/**
 * @a https://leetcode.cn/problems/Jf1JuT/
 */

#include "../../common.h"

class Solution {
    unordered_map<char,unordered_set<char>> edges;
    unordered_map<char,int> in_degree;
    bool is_same_prefix = false;
public:
    string alienOrder(vector<string>& words) {
        // init in_degree
        for(auto &str:words){
            for(char ch : str){
                in_degree[ch] = 0;
            }
        }

        int nr_word = words.size();
        for(int i = 0; i < nr_word - 1; ++i){
            for(int j = i + 1; j < nr_word; ++j){
                add(words[i], words[j]);    // 建邻接表
                if(is_same_prefix) return "";
            }
        }

        // topological sort
        queue<char> que;
        for(auto &[ch, degree] : in_degree){
            if(degree == 0) que.push(ch);
        }
        string ret;
        while(que.size()){
            char t = que.front(); que.pop();
            ret += t;
            for(auto ch : edges[t]){
                if(--in_degree[ch] == 0) que.push(ch);
            }
        }
        if(in_degree.size() != ret.size()) return "";
        return ret;
    }
    void add(string& s1, string& s2){
        int sz = min(s1.size(),s2.size());
        int i = 0;
        while(i < sz){
            char src = s1[i], dst = s2[i];
            if(src != dst){
                if(!edges.count(src) || !edges[src].count(dst))
                {
                    edges[src].insert(dst);
                    ++in_degree[dst];    
                }
                break;
            }
            ++i;
        }//same prefix s2 must shortest
        if(i == s2.size() && i < s1.size()) is_same_prefix = true;
    }
};